from queue import LifoQueue


class Solution1:
    def scoreOfParentheses(self, s):
        """
        :type S: str
        :rtype: int
        """
        
        def go(s):
            if not s:
                return 1
            h = 0
            for i in range(len(s)):
                if '(' == s[i]:
                    h += 1
                else:
                    h -= 1
                if 0 == h:
                    break
            return 2 * go(s[1:i]) + (0 if (i + 1 >= len(s)) else go(s[i + 1:]))
        
        return go(s) // 2


class Solution:
    def scoreOfParenthesesCore(self, S):
        if not S:
            return 1
        h = 0
        for i in range(len(S)):
            if S[i] == "(":
                h += 1
            elif S[i] == ")":
                h -= 1
            if h == 0:
                break
        return 2 * self.scoreOfParenthesesCore(S[1:i]) + (0 if i + 1 >= len(S) else self.scoreOfParenthesesCore(S[i + 1:]))
    
    def scoreOfParentheses(self, S):
        """
        :type S: str
        :rtype: int
        """
        return self.scoreOfParenthesesCore(S) // 2


def main():
    sol = Solution()
    print(sol.scoreOfParentheses("(()())()()"))


if __name__ == "__main__":
    main()
